Kelly sinh tại Günzburg, Bayern, Đức (lúc đó là "Khu vực do Đồng minh (Hoa Kỳ) chiếm đóng",) năm 1947, dưới tên Petra Karin Lehmann. Bà đổi tên thành Kelly sau khi người mẹ của bà kết hôn với một sĩ quan thuộc Quân đội Hoa Kỳ. Bà được giáo dục trong một nữ tu viện Công giáo ở Günzburg, rồi theo học trường ở Georgia và Virginia sau khi gia đình di chuyển về Hoa Kỳ năm 1959. Bà sống và học ở Mỹ cho tới khi trở về Tây Đức năm 1970. Bà vẫn giữ quốc tịch (Tây) Đức của mình suốt đời.

Là người ngưỡng mộ Martin Luther King, Jr., bà đã tham gia vận động cho Robert F. Kennedy và Hubert Humphrey trong cuộc bầu cử tổng thống Hoa Kỳ năm 1968. Bà học khoa học chính trị ở School of International Service thuộc Đại học Hoa Kỳ (Washington, DC), và tốt nghiệp năm 1970. Năm 1971, bà tốt nghiệp "Học viện châu Âu" (European Institute) của Đại học Amsterdam năm 1971.

Khi làm việc ở Ủy ban châu Âu (Bruxelles, Bỉ, 1971–83), bà đã tham gia rất nhiều cuộc vận động cho hòa bình và môi trường tại Đức cùng các nước khác.